#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
using namespace std;

class Solution1
{
public:
    int maximumSum(vector<int>& arr)
    {
        int n = arr.size();
        vector<int> f(n);
        auto g = f;
        f[0] = arr[0], g[0] = 0;
        int ret = f[0];
        for (int i = 1; i < n; ++i)
        {
            f[i] = max(f[i - 1] + arr[i], arr[i]);
            g[i] = max(f[i - 1], g[i - 1] + arr[i]);
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

class Solution2
{
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
    {
        int n = books.size();
        vector<int> dp(n + 1, 1e6);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            int maxHeight = 0, curWidth = 0;
            for (int j = i - 1; j >= 0; --j)
            {
                curWidth += books[j][0];
                if (curWidth > shelfWidth) break;

                maxHeight = max(maxHeight, books[j][1]);
                dp[i] = min(dp[i], dp[j] + maxHeight);
            }
        }
        return dp[n];
    }
};